package demo2;

class ListNode {
    int val;
    ListNode next = null;
  }

public class IsPalindrome {
    public static void main(String[] args) {
        ListNode l1 = new ListNode();
        l1.val = 1;
        ListNode l2 = new ListNode();
        l2.val = 2;
        l1.next = l2;
        isPalindrome(l1);
    }
    public static boolean isPalindrome (ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        ListNode fast = head, slow = head, prev = null;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            prev = slow;
            slow = slow.next;
        }

        ListNode cur = slow, next = slow.next;
        while(cur != null) {
            cur.next = prev;
            prev = cur;
            cur = next;
            if(cur != null) {
                next = cur.next;
            }
        }

        ListNode left = head, right = prev;
        while(left != right && right.next != left) {
            if(left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return left.val == right.val;
    }
}
